package leecode

import "sort"

type MyCalendarThree struct {
	diff map[int]int //差分数组
}

func Constructor732() MyCalendarThree {
	return MyCalendarThree{diff: make(map[int]int)}
}

func (this *MyCalendarThree) Book(startTime int, endTime int) int {
	//开始日期加1
	this.diff[startTime]++
	//结束日期减1
	this.diff[endTime]--
	keys := make([]int, 0, len(this.diff))
	for k := range this.diff {
		keys = append(keys, k)
	}
	sort.Ints(keys)

	res := 0
	cur := 0
	for _, k := range keys {
		cur += this.diff[k] // 还原原数组，由于初始值都是0所以这里就只是加差分值
		if cur > res {
			res = cur // 求预定次数的最大值
		}
	}
	return res
}
